import java.util.ArrayList;
import java.util.Random;

class TreeNode {
	Move move;
	int value;

	public TreeNode(Move moves, int values){
		move = moves;
		value = values;
	}
}


public class MinMax implements Piece {
	Board board;
	int numMovesPlayed;
	int maxDepth=6;
	int player;
	int opponent;
	
	public MinMax(Board boardInput, int numMoves, int p, int o) {
		board = boardInput;
		numMovesPlayed = numMoves;
		player = p;
		opponent = o;
	}
	
	// This is a recursive function that calculates and returns a move
	// using minimax with alpha beta pruning.
	private TreeNode chooseMove(int P, Board boardState, int depth,
			int alpha, int beta){
		TreeNode child;
		TreeNode fakeBest;
		TreeNode myBest = new TreeNode(null, Integer.MIN_VALUE);
		
		ArrayList<Move> moves = new ArrayList<Move>();
		moves = boardState.possibleMoves(P);
		
		if (depth == maxDepth || boardState.numEmpty() == 0) {
			fakeBest = new TreeNode(null, evaluateBoard(boardState, player));
			return fakeBest;
		}
				
		if (P == player) {
			myBest.value = alpha;
			for (int i=0; i<moves.size();i++) {
				Board tempBoard = new Board(boardState.size);
				
				for (int row=0; row<tempBoard.size; row++) {
					for (int col=0; col<tempBoard.size; col++) {
						tempBoard.board[row][col] = boardState.board[row][col];
					}
				}
				
				tempBoard.insertMove(moves.get(i));
				
				child = chooseMove(opponent,tempBoard,depth+1,alpha,beta);
				
				if (child.value > alpha){
					alpha = child.value;
					myBest.value = child.value;
					myBest.move = moves.get(i);
				}
				
				if (beta<=alpha) {
					break;
				}
			}
			return myBest;
		}else {
			myBest.value = beta;
			for (int i=0; i<moves.size();i++) {
				Board tempBoard = new Board(boardState.size);
				
				for (int row=0; row<tempBoard.size; row++) {
					for (int col=0; col<tempBoard.size; col++) {
						tempBoard.board[row][col] = boardState.board[row][col];
					}
				}
				
				tempBoard.insertMove(moves.get(i));
				child = chooseMove(player,tempBoard,depth+1,alpha,beta);
				
				if (child.value < beta){
					beta = child.value;
					myBest.value = child.value;
					myBest.move = moves.get(i);
				}
				
				if (beta<=alpha) {
					break;
				}
			}
			return myBest;
		}
		
	}
	
	// Returns a value of the current board state for
	// player P for leaf node in minimax tree.
	private int evaluateBoard(Board board, int P) {
		return board.numPlayerPieces(P)-board.numPlayerPieces(opponent);
	}
	
	// Returns the best move from the current board state
	// using minimax with alpha beta pruning
	public Move bestMove() {
		TreeNode bestMove = chooseMove(player, board, 0, 
				Integer.MIN_VALUE, Integer.MAX_VALUE);
		board.insertMove(bestMove.move);
		return bestMove.move;
	}
	
	// Returns random move from the current board state
	public Move averageMove() {
		ArrayList<Move> moves = new ArrayList<Move>();
		moves = board.possibleMoves(player);
		
		Random rand = new Random();
		int n = rand.nextInt(moves.size());
		
		board.insertMove(moves.get(n));
		
		return moves.get(n);
	}
}
